// 17.3 正则表达式
/**
 * 正则表达式（regular expression）是一种描述字符序列的方法，是一种极其强大的计算工具。但是，用于定义正则表达式的描述语言已经大大超出了本书的范围。
 *   因此，我们重点介绍如何使用C++正则表达式库（RE库），它是新标准库的一部分。RE库定义在头文件regex中，它包含多个组件，列于表17.4中。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <memory>
#include <new>
using namespace std;
#include <functional>
#include "../VisualStudio2012/15/Quote.h"
#include "../VisualStudio2012/12/TextQuery.h"
#include <tuple>
#include <bitset>
#include <regex>

int main()
{
    // 17.3 正则表达式
    /*
正则表达式（regular expression）是一种描述字符序列的方法，是一种极其强大的计算工具。但是，用于定义正则表达式的描述语言已经大大超出了本书的范围。
  因此，我们重点介绍如何使用C++正则表达式库（RE库），它是新标准库的一部分。RE库定义在头文件regex中，它包含多个组件，列于表17.4中。
regex           表示有一个正则表达式的类
regex_match     将一个字符序列与一个正则表达式匹配
regex_search    寻找第一个与正则表达式匹配的子序列
regex_replace   使用给定格式替换一个正则表达式
sregex_iterator 迭代器适配器，调用regex_search()来遍历一个string中所有的子串
smatch          容器类，保存在string中搜索的结果
ssbu_match      string中匹配的子表达式的结果
regex类表示一个正则表达式。除了初始化和赋值之外，regex还支持其他一些操作。表17.6（第647页）列出了regex支持的操作。
函数regex_match和regex_search确定一个给定字符序列与一个给定regex是否匹配。如果整个输入序列与表达式匹配，则regex_match函数返回true；如果输入序列中一个子串与表达式匹配，则regex_search函数返回true。
    */

    // 17.3.1 使用正则表达式库
    /*
// 查找不在字符c之后的字符串ei
string pattern("[^c]ei");
pattern = "[[:alpha:]]*" + pattern + "[[:alpha:]]*";
regex r(pattern); // 构造一个用于查找模式的regex
smatch results;   // 顶一个一个对象保存搜索结果
// 定义一个string保存于模式匹配和不匹配的文本
string test_str = "receipt freind theif receive";
// 用r在test_str中查找于pattern匹配的子串
if(regex_search(test_str, results, r)) // 如果有子串匹配
    cout << results.str() << endl;     // 打印匹配的单词
正则表达式[^c]表明我们希望匹配任意不是'c'的字符，而[^c]ei指出我们想要匹配这种字符后接ei的字符串。
默认情况下，regex使用的正则表达式语言是ECMAScript。在ECMAScript中，模式[[：：alpha：]]匹配任意字母，符号+和＊分别表示我们希望“一个或多个”或“零个或多个”匹配。
  因此[[：：alpha：]]＊将匹配零个或多个字母。
    */

    // 指定regex对象的选项
    /*
当我们定义一个regex或是对一个regex调用assign为其赋予新值时，可以指定一些标志来影响regex如何操作。这些标志控制regex对象的处理过程。表17.6列出的最后6个标志指出编写正则表达式所用的语言。
  对这6个标志，我们必须设置其中之一，且只能设置一个。默认情况下，ECMAScript标志被设置，从而regex会使用ECMA-262规范，这也是很多Web浏览器所使用的正则表达式语言。
regex r(re)      re表示一个正则表达式，它可以是一个string、一个表示字符范围的迭代器对、一个指向空字符结尾的字符数组的指针、
regex r(re, f)   一个字符指针和一个计数器或是一个花括号包围的字符列表。f是指出对象如何处理的标志。f通过下面列出的值来设置。如果未指定f，其默认值为ECMAScript
r1 = re          将r1中的正则表达式替换为re。re是一个正则表达式，它可以是另一个regex对象、一个string、一个指向空字符结尾的字符数组的指针或是一个花括号包围的字符列表
r1.assign(re, f) 与使用赋值运算符（=）效果相同，可选的标志f也与regex的构造函数中对应的参数含义相同
r.mark_count()   r中子表达式的数目（17.3.3节）
r.flags()        返回r的标志集
注：构造函数和赋值操作可能抛出类型为regex_error的异常
定义regex时指定的标志
定义在regex和regex_constants::syntax_option_type中
icase            在匹配过程中忽略大小写
nosubs           不保存匹配的子表达式
optimize         执行速度优先于构造速度
ECMAScript       使用ECMA-262指定的语法
basic            使用POSIX基本的正则表达式语法
extended         使用POSIX扩展的正则表达式语法
awk              使用POSIX版本的AWK语言的语法
grep             使用POSIX版本的grep的语法
egrep            使用POSIX版本的egrep的语法
作为一个例子，我们可以用icase标志查找具有特定扩展名的文件名。大多数操作系统都是按大小写无关的方式来识别扩展名的——可以将一个C++程序保存在.cc结尾的文件中，
  也可以保存在.Cc、.cC或是.CC结尾的文件中，效果是一样的。
// 一个或多个字母或数字字符后接一个‘.’再接“cpp”或“cxx”或“cc”
regex r("[[:alnum:]]+\\.(cpp|cxx|cc)$", regex::icase);
smatch results;
string filename;
while(cin >> filename)
    if(regex_search(filename, results, r))
        cout << filename << " is a C++ source file" << endl; // 打印匹配的文件名
就像C++语言中有特殊字符一样（参见2.1.3节，第36页），正则表达式语言通常也有特殊字符。例如，字符点（.）通常匹配任意字符。与C++一样，我们可以在字符之前放置一个反斜线来去掉其特殊含义。
  由于反斜线也是C++中的一个特殊字符，我们在字符串字面常量中必须连续使用两个反斜线来告诉C++我们想要一个普通反斜线字符。
  因此，为了表示与句点字符匹配的正则表达式，必须写成\\.（第一个反斜线去掉C++语言中反斜线的特殊含义，即，正则表达式字符串为\.，第二个反斜线则表示在正则表达式中去掉.的特殊含义）。
    */

    // 指定或使用正则表达式时的错误
    // 需要意识到的非常重要的一点是，一个正则表达式的语法是否正确是在运行时解析的。
    /*
如果我们编写的正则表达式存在错误，则在运行时标准库会抛出一个类型为regex_error的异常（参见5.6节，第173页）。类似标准异常类型，regex_error有一个what操作来描述发生了什么错误（参见5.6.2节，第175页）。
  regex_error还有一个名为code的成员，用来返回某个错误类型对应的数值编码。code返回的值是由具体实现定义的。RE库能抛出的标准错误如表17.7所示。
try {
    // 错误：alnum漏掉了右括号，构造函数会抛出异常
    regex r("[[:alnum:]+\\.(cpp|cxx|cc)$", regex::icase);
} catch (regex_error e)
{ cout << e.what() << "\ncode: " << e.code() << endl; }
表17.7 正则表达式错误类型
error_collate      无效的元素校对请求
error_ctype        无效的字符类
error_escape       无效的转义字符或无效的尾置转义
error_backref      无效的反向引用
error_brack        不匹配的方括号（[或]）
error_paren        不匹配的圆括号（(或)）
error_brace        不匹配的花括号（{或}）
error_badbrace     花括号{}中无效的范围
error_range        无效的字符范围，如（[z-a]）
error_space        内存不足，无法处理此正则表达式（正则表达式字符串过长？）
error_badrepeat    重复字符（*、?、+或{）之前没有有效的正则表达式
error_complexity   要求的匹配过于复杂（正则表达式过于复杂）
error_stack        栈空间不足，无法处理匹配（正则表达式的递归深度过深？）
    */

    // 建议：避免创建不必要的正则表达式
    /*如我们所见，一个正则表达式所表示的“程序”是在运行时而非编译时编译的。正则表达式的编译是一个非常慢的操作，特别是在你使用了扩展的正则表达式语法或是复杂的正则表达式时。
        因此，构造一个regex对象以及向一个已存在的regex赋予一个新的正则表达式可能是非常耗时的。为了最小化这种开销，你应该努力避免创建很多不必要的regex。
        特别是，如果你在一个循环中使用正则表达式，应该在循环外创建它，而不是在每步迭代时都编译它。
    */

    // 正则表达式类和输入序列类型
    /*
    我们可以搜索多种类型的输入序列。输入可以是普通char数据或wchar_t数据，字符可以保存在标准库string中或是char数组中（或是宽字符版本，wstring或wchar_t数组中）。
      RE为这些不同的输入序列类型都定义了对应的类型。例如，regex类保存类型char的正则表达式。标准库还定义了一个wregex类保存类型wachar_t，其操作与regex完全相同。
      两者唯一的差别是wregex的初始值必须使用wchar_t而不是char。
    smatch表示string类型的输入序列；cmatch表示字符数组序列；wsmatch表示宽字符串（wstring）输入；而wcmatch表示宽字符数组。
regex r("[[:alnum:]]+\\.(cpp|cxx|cc)$", regex::icase);
smatch results; // 将匹配string输入序列，而不是char*
if(regex_search("myfile.cc", r)) // 错误：输入为char*
    cout << results.str() << endl;
这段代码会编译失败，因为match参数的类型与输入序列的类型不匹配。如果我们希望搜索一个字符数组，就必须使用cmatch对象：
cmatch results; // 将匹配字符数组输入序列
if(regex_search("myfile.cc", r))
    cout << results.str() << endl;
表17.8 正则表达式类库
如果输入序列类型      则使用正则表达式类
string               regex、smatch、ssub_match和sregex_iterator
const char*          regex、cmatch、csub_match和cregex_iterator
wstring              wregex、wsmatch、wssub_match和wsregex_iterator
const wchar_t*       wregex、wcmatch、wcsub_match和wcregex_iterator
    */

    // 17.3.2 匹配与Regex迭代器类型
    /*
    regex迭代器是一种迭代器适配器（参见9.6节，第329页），被绑定到一个输入序列和一个regex对象上。如表17.8所述，每种不同输入序列类型都有对应的特殊regex迭代器类型。迭代器操作如表17.9所述。
表17.9 sregex_iterator操作
这些操作也适用于cregex_iterator、wsregex_iterator和wcregex_iterator。
操作                   说明
sregex_iterator         一个sregex_iterator，遍历迭代器b和e表示的string
it(b, e, r);            它调用sregex_search(b, e, r)将it定位到输入中第一个匹配的位置
sregex_iterator end;    sregex_iterator的尾后迭代器      
*it                     根据最后一个调用regex_search的结果，返回一个smatch对象的引用或一个指向smatch对象的指针
it->
++it                    从输入序列当前匹配位置开始调用regex_search。前置版本返回递增后迭代器，后置版本返回旧值
it++
it1 == it2              如果两个sregex_iterator都是尾后迭代器，则他们相等两个
it1 != it2              非尾后迭代器是从相同的输入序列和regex对象构造，则他们相等
当我们将一个sregex_iterator绑定到一个string和一个regex对象时，迭代器自动定位到给定string中第一个匹配位置。即，sregex_iterator构造函数对给定string和regex调用regex_search。
  当我们解引用迭代器时，会得到一个对应最近一次搜索结果的smatch对象。当我们递增迭代器时，它调用regex_search在输入string中查找下一个匹配。
    */
    
    // 使用sregex_iterator
    /*作为一个例子，我们将扩展之前的程序，在一个文本文件中查找所有违反“i在e之前，除非在c之后”规则的单词。我们假定名为file的string保存了我们要搜索的输入文件的全部内容。
      这个版本的程序将使用与前一个版本一样的pattern，但会使用一个sregex_iterator来进行搜索：
// 查找前一个字符不是c的字符串ei
string pattern("[^c]ei");
// 我们想要包含pattern的单词的全部内容
pattern = "[[:alpha:]]*+" + pattern + "[[:alpha:]]*";
regex r(pattern, regex::icase); // 在进行匹配时将忽略大小写
// 它将反复调用regex_search来寻找文件中的所有匹配
for(sregex_iterator it(file.begin(), file.end(), r), end_it; it!= end_it; ++it)
    cout << it->str() << endl; // 匹配的单词
    */

    // 使用匹配数据
    /*我们将在下一节中介绍更多有关smatch和ssub_match类型的内容。目前，我们只需知道它们允许我们获得匹配的上下文即可。匹配类型有两个名为prefix和suffix的成员，
        分别返回表示输入序列中当前匹配之前和之后部分的ssub_match对象。一个ssub_match对象有两个名为str和length的成员，分别返回匹配的string和该string的大小。我们可以用这些操作重写语法程序的循环。
for(sregex_iterator it(file.begin(), file.end(), r), end_it; it!= end_it; ++it) {
    auto pos = it->prefix().length(); // 前缀的大小
    pos = pos > 40 ? pos -40 : 0;     // 我们想要最多40个字符
    cout << it->prefix().str().substr(pos)        // 前缀的最后一部分
         << "\n\t\t>>> " << it->str() << " <<<\n" // 匹配的单词
         << it->suffix().str().substr(0, 40)      // 后缀的第一部分
         << endl; 
}
我们调用prefix，返回一个ssub_match对象，表示file中当前匹配之前的部分。我们对此ssub_match对象调用length，获得前缀部分的字符数目。接下来调整pos，使之指向前缀部分末尾向前40个字符的位置。
  如果前缀部分的长度小于40个字符，我们将pos置为0，表示要打印整个前缀部分。我们用substr（参见9.5.1节，第321页）来打印指定位置到前缀部分末尾的内容。
表17.10 smatch操作
这些操作也适用于cmatch、wsmatch、wcmatch和对应的csub_match、wssub_match、wcsub_match
m.ready()             如果已经通过调用regex_search或regex_match设置了m，则返回true，否则返回false
                      如果ready返回fanlse，则对m进行操作是未定义的
m.size()              如果匹配失败，则返回0。否则返回最近一次匹配的正则表达式中子表达式的数目
m.empty()             若m.size()为0，则返回true，否则返回false
m.prefix()            一个ssub_match对象，表示当前匹配之前的序列
m.suffix()            一个ssub_match对象，表示当前匹配之后的部分
m.format(...)         见表17.12
在接受一个索引的操作中，n的默认值为0且必须小于m.size()。
第一个子匹配（索引为0）表示整个匹配。
m.length(n)           第n个匹配的子表达式的大小
m.position(n)         第n个子表达式距序列开始的距离
m.str(n)              第n个子表达式匹配的string
m[n]                  对应第n个子表达式的ssub_match对象
m.begin(), m.end()    表示m中sub_match元素范围的迭代器。
m.cbegin(), m.cend()  
    */

    // 17.3.3 使用子表达式
    /*正则表达式中的模式通常包含一个或多个子表达式（subexpression）。一个子表达式是模式的一部分，本身也具有意义。正则表达式语法通常用括号表示子表达式。
        例如，我们用来匹配C++文件的模式（参见17.3.1节，第646页）就是用括号来分组可能的文件扩展名。每当我们用括号分组多个可行选项时，同时也就声明了这些选项形成子表达式。
        我们可以重写扩展名表达式，以使得模式中点之前表示文件名的部分也形成子表达式，如下所示：[插图]
// r有两个子表达式：第一个是点之前表示文件名的部分，第二个表示文件扩展名
regex r("([[:alnum:]]+)\\.(cpp|cxx|cc)$", regex::icase);
      匹配对象除了提供匹配整体的相关信息外，还提供访问模式中每个子表达式的能力。子匹配是按位置来访问的。第一个子匹配位置为0，表示整个模式对应的匹配，随后是每个子表达式对应的匹配。
    */

    // 子表达式用于数据验证
    /*例如，美国的电话号码有十位数字，包含一个区号和一个七位的本地号码。区号通常放在括号里，但这并不是必需的。剩余七位数字可以用一个短横线、一个点或是一个空格分隔，但也可以完全不用分隔符。
        我们可能希望接受任何这种格式的数据而拒绝任何其他格式的数。我们将分两步来实现这一目标：首先，我们将用一个正则表达式找到可能是电话号码的序列，然后再调用一个函数来完成数据验证。
      ECMAScript正则表达式语言的一些特性：
        · \{d}表示单个数字而\{d}{n}则表示一个n个数字的序列。（如，\{d}{3}匹配三个数字的序列。）
        · 在方括号中的字符集合表示匹配这些字符中任意一个。（如，[-.]匹配一个短横线或一个点或一个空格。注意，点在括号中没有特殊含义。）
        · 后接'？'的组件是可选的。（如，\{d}{3}[-.]？\{d}{4}匹配这样的序列：开始是三个数字，后接一个可选的短横线或点或空格，然后是四个数字。
          此模式可以匹配555-0132或555.0132或555 0132或5550132。）
        · 类似C++，ECMAScript使用反斜线表示一个字符本身而不是其特殊含义。由于我们的模式包含括号，而括号是ECMAScript中的特殊字符，因此我们必须用\（和\）来表示括号是我们的模式的一部分而不是特殊字符。
      由于反斜线是C++中的特殊字符，在模式中每次出现\的地方，我们都必须用一个额外的反斜线来告知C++我们需要一个反斜线字符而不是一个特殊符号。因此，我们用\\{d}{3}来表示正则表达式\{d}{3}。
      为了获得匹配的组成部分，我们需要在定义正则表达式时使用子表达式。每个子表达式用一对括号包围：[插图]
// 整个正则表达式包含七个子表达式
"(\\()?(\\{d}{3})(\\))?([-. ])?(\\d{3})([-. ]?)(\\{d}{4})";
下面的代码读取一个文件，并用此模式查找与完整的电话号码模式匹配的数据。它会调用一个名为valid的函数来检查号码格式是否合法：[插图]
string phone = "(\\()?(\\{d}{3})(\\))?([-. ])?(\\d{3})([-. ]?)(\\{d}{4})";
regex r(phone);
smatch m;
string s;
while(geline(cin, s))
    for(sregex_iterator it(s.begin(), s.end(), r), end_it; it!= end_it; ++it)
        if(valid(*it))
            cout << "valid: " << it->str() << endl;
        eles
            cout << "invalid: " << it->str() << endl;
    */

    // 使用子匹配操作
    /*我们将使用表17.11中描述的子匹配操作来编写valid函数。需要记住的重要一点是，我们的pattern有七个子表达式。与往常一样，每个smatch对象会包含八个ssub_match元素。
        位置[0]的元素表示整个匹配；元素[1]…[7]表示每个对应的子表达式。
      在一个合法的电话号码中，区号要么是完整括号包围的，要么完全没有括号。因此，valid要做什么工作依赖于号码是否以一个括号开始：
bool valid(const smatch& m)
{
    // 如果区号前有一个左括号
    if(m[1].matched)
        // 则区号后必有一个右括号，之后紧跟剩余号码或一个空格
        return m[3].matched && (m[4].matched == 0 || m[4].str() == " ");
    else
        // 否则，区号后不能有右括号；另两个组成部分间的分隔符必须匹配
        return !m[3].matched && m[4].str() == m[6].str();
}
    */

    // 17.3.4 使用regex_replace
    /*当我们希望在输入序列中查找并替换一个正则表达式时，可以调用regex_replace。表17.12描述了regex_replace，类似搜索函数，它接受一个输入字符序列和一个regex对象，不同的是，
        它还接受一个描述我们想要的输出形式的字符串。
表17.12 正则表达式替换操作
m.format(dest, fmt, mft)              使用格式字符串fmt生成格式化输出，匹配在m中，可选的match_flag_type标志在mft中。第一个版本写入迭代器dest指向的目的位置（参见10.5.1节，第365页）并接受fmt参数，
                                      可以是一个string，也可以是表示字符数组中范围的一对指针。第二个版本返回一个string，保存输出，并接受fmt参数，可以是一个string，
m.format(fmt, mft)                    也可以是一个指向空字符结尾的字符数组的指针。mft的默认值为format_default

regex_replace(dest, seq, r, fmt, mft) 遍历seq，用regex_search查找与regex对象r匹配的子串。使用格式字符串fmt和可选的match_flag_type标志来生成输出。第一个版本将输出写入到迭代器dest指定的位置，
regex_replace(seq, r, fmt, mft)       并接受一对迭代器seq表示范围。第二个版本返回一个string，保存输出，且seq既可以是一个string也可以是一个指向空字符结尾的字符数组的指针。
                                      在所有情况下，fmt既可以是一个string也可以是一个指向空字符结尾的字符数组的指针，且mft的默认值为match_default
      替换字符串由我们想要的字符组合与匹配的子串对应的子表达式而组成。在本例中，我们希望在替换字符串中使用第二个、第五个和第七个子表达式。而忽略第一个、第三个、第四个和第六个子表达式，
        因为这些子表达式用来形成号码的原格式而非新格式中的一部分。我们用一个符号$后跟子表达式的索引号来表示一个特定的子表达式：[插图]
string fmt = "$2.$5.$7"; // 将号码格式改为ddd.ddd.dddd
regex r(phone);
string number = "(908) 555-1800";
cout << regex_replace(number, r, fmt) << endl;
    */

    // 只替换输入序列的一部分

    // 用来控制匹配和格式的标志
    /*就像标准库定义标志来指导如何处理正则表达式一样，标准库还定义了用来在替换过程中控制匹配或格式的标志。表17.13列出了这些值。
        这些标志可以传递给函数regex_search或regex_match或是类smatch的format成员。
      匹配和格式化标志的类型为match_flag_type。这些值都定义在名为regex_constants的命名空间中。类似用于bind的placeholders（参见10.3.4节，第355页），
        regex_constants也是定义在命名空间std中的命名空间。为了使用regex_constants中的名字，我们必须在名字前同时加上两个命名空间的限定符：[插图] using std::regex_constants::format_no_copy;
        此声明指出，如果代码中使用了format_no_copy，则表示我们想要使用命名空间std：：constants中的这个名字。如下所示，我们也可以用另一种形式的using来代替上面的代码，我
        们将在18.2.2节（第702页）中介绍这种形式：[插图] using namespace std::regex_constants;
表17.13 匹配标志
定义在regex_constants::match_flag_type中
match_default                       等价于format_default。匹配标志的默认值。
match_not_bol                       不将首字符作为行首处理
match_not_eol                       不将尾字符作为行尾处理
match_not_bow                       不将首字符作为单词首处理
match_not_eow                       不将尾字符作为单词尾处理
match_any                           如果存在多余一个匹配，则可返回任意一个匹配
match_not_null                      不匹配任何空序列
match_continuous                    匹配必须从输入的首字符开始
match_prev_avail                    输入序列包含第一匹配之前的内容
format_default                      用ECMAScript规则替换字符串
format_sed                          用POSIX sed规则替换字符串
format_no_copy                      不输出输入序列中未匹配的部分
format_first_only                   只替换子表达式的第一次出现
    */

    // 使用格式标志
    /*默认情况下，regex_replace输出整个输入序列。未与正则表达式匹配的部分会原样输出；匹配的部分按格式字符串指定的格式输出。我们可以通过在regex_replace调用中指定format_no_copy来改变这种默认行为：
// 只生成电话号码：使用新的格式字符串
string fmt2 = "$2.$5.$7 "; // 在最后一部分号码后放置空格作为分隔符 
// 通知regex_repalce只拷贝它替换的文本
cout << regex_replace(s, r, fmt2, format_no_copy) << endl;
    */

    return 0;
}